/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 言初
 * Date: 2023-11-15
 * Time: 22:08
 */
import java.util.*;


// 725. 分隔链表



class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}


public class test {
    public static void main(String[] args) {
        System.out.println();
    }
    public ListNode[] splitListToParts(ListNode head, int k) {
        //先求出head这个链表的长度，继而得到分割后的每个子链表的长度
        int len=0;
        ListNode ret=head;
        while(ret!=null){
            len++;
            ret=ret.next;
        }

        int num=len/k;//商
        int remainder=len%k;//余数
        //按照题目要求：排在前面的部分的长度应该大于或等于排在后面的长度。
        //所以说这个余数的部分应该用在前面，就是举个例子：
        //假如有11个数，需要分成3份，那么num=3,remainder=2,也就是说会被分成【4，4，3】这样的三份，也就是说，作为余数的remainder分给了前面的部分

        ListNode[] list=new ListNode[k];
        //如果num的值==0，那就说明，把原链表分割后，每一个节点作为了一个新的部分放到节点数组中去
        ret=head;
        int i=0;


        if(num==0){
            while(ret!=null){
                list[i]=ret;
                ret=ret.next;
                list[i].next=null;
                i++;
            }
        }
        // 如果num的值！=0，那就说明，需要把原链表分割成每一份都是num大小的放到节点数组中去（这种情况需要考虑余数的使用）
        //假如有11个数，需要分成3份，那么num=3,remainder=2,也就是说会被分成【4，4，3】这样的三份，也就是说，作为余数的remainder分给了前面的部分
        else{
            int sum=1;//表征找到的 这个中间形态的链表的长度
            ListNode newHead=null;//新的中间链表的 头结点
            ListNode cur=null;//新的中间 表征新的中间链表的 当前位置的节点

            //使用while循环遍历这个链表
            while(ret!=null){
                //有余数的情况，把余数一个一个的分给链表数组中前面的位置,让前面位置的子链表的长度变成了：num+1
                if(remainder>0){
                    if(sum<=num+1){
                        if(sum==1){
                            //新的中间子链表的头结点为空的情况
                            newHead=ret;
                            cur=ret;
                        }else{
                            //新的中间子链表的头结点 不为空 的情况
                            cur.next=ret;
                            cur=ret;
                        }
                        sum++;
                        //ret往下走
                        ret=ret.next;
                    }

                    else{
                        //走到这里，就代表sum==num+1,一个子链表寻找完成，开始加入链表数组 以及 复原变量

                        cur.next=null;//每个子链表之间不再关联，所以需要把next置为null
                        list[i++]=newHead;//加入链表数组中

                        //复原变量
                        sum=1;
                        newHead=null;
                        cur=null;

                        //每次找完一个子链表，余数都要--，代表用完一个余数的值了
                        remainder--;
                    }
                }

                //没有余数的情况,那就每一份的子链表的长度都是相等的num就行了
                else{
                    if(sum<=num){
                        if(sum==1){
                            //新的中间子链表的头结点为空的情况
                            newHead=ret;
                            cur=ret;
                        }else{
                            //新的中间子链表的头结点 不为空 的情况
                            cur.next=ret;
                            cur=ret;
                        }
                        sum++;
                        //ret继续往下走
                        ret=ret.next;
                    }

                    //走到这里，就代表sum==num,一个子链表寻找完成，开始加入链表数组 以及 复原变量
                    else{


                        cur.next=null;//每个子链表之间不再关联，所以需要把next置为null
                        list[i++]=newHead;//加入链表数组中

                        //复原变量
                        sum=1;
                        newHead=null;
                        cur=null;
                    }
                }

            }
            list[i]=newHead;//最后的这个还没有加进去，就因为遍历到链表的末尾而跳出循环 了，所以在这里要把最后这一段加到链表数组list中
        }
        return list;
    }
}
